0718. 最长重复子数组【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 动态规划

1. 📝 题目描述

• leetcode

给两个整数数组 nums1 和 nums2，返回两个数组中 公共的 、长度最长的子数组的长度。

---

示例 1：

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1]。

示例 2：

输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

---

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 100

2. 🎯 s.1 - 动态规划

c

int findLength(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int** dp = (int**)malloc(sizeof(int*) * (nums1Size + 1));
    for (int i = 0; i <= nums1Size; i++) dp[i] = (int*)calloc(nums2Size + 1, sizeof(int));
    int res = 0;
    for (int i = 1; i <= nums1Size; i++) {
        for (int j = 1; j <= nums2Size; j++) {
            if (nums1[i - 1] == nums2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if (dp[i][j] > res) res = dp[i][j];
            }
        }
    }
    for (int i = 0; i <= nums1Size; i++) free(dp[i]);
    free(dp);
    return res;
}

js

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findLength = function (nums1, nums2) {
  const m = nums1.length,
    n = nums2.length
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0))
  let res = 0
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (nums1[i - 1] === nums2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1
        if (dp[i][j] > res) res = dp[i][j]
      }
    }
  }
  return res
}

py

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        res = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if nums1[i - 1] == nums2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    res = max(res, dp[i][j])
        return res

• 时间复杂度：$O(m\times n)$，其中 m 和 n 分别是两个数组的长度
• 空间复杂度：$O(m\times n)$

算法思路：

• dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组长度
• 元素相等时 dp[i][j] = dp[i-1][j-1] + 1，否则为 0
• 遍历过程中记录最大值即为答案